%\section{ECC Design for Memristor Based ReRAM}\label{sec:mathematical}
\section{Error estimation and ECC design for Memristor-Based ReRAM}\label{sec:mathematical}
In this section, we first present the mathematical model of error pattern of the memristor-based ReRAM cell. Then the data error rate of the memristor memory array is analyzed in detail.

\subsection{Memristor Model}
%\begin{figure}
%\centering
%  % Requires \usepackage{graphicx}
%  \includegraphics[width=0.35\textwidth]{./figures/memristor_model.pdf}\\
%  \vspace{-10pt}
%  \caption{Circuit model of memristor cells.}\label{fig:model}
%  \vspace{-15pt}
%\end{figure}
The switching mechanisms of the memristor have been analyzed in detail based on the experimental results by Yang~\cite{memristor:mechanism}. Yang's study suggested that, the resistance switching is mainly caused by the shunting and recovery of the electronic barrier at the metal-oxide interface. However, the two interfaces (metal-$TiO_2$ and $TiO_{2-x}$-metal) have different roles in terms of switching behaviors. The top interface (metal-$TiO_{2}$) has the Schottky-like behavior due to its high doping rate. On the other hand, the bottom interface ($TiO_{2-x}$-metal) has low doping and is ohmic-like. The combination of these two behaviors is shown in Figure~\ref{fig:structures}. Therefore, it can be concluded that the interface with Schottky-like behavior dominates the switching behaviors of the memristor cell. Based on the
different mechanisms in the metal-oxide interfaces, the I-V switching
characteristic can be modeled as:
\begin{eqnarray}
\label{equ:model_two_inter}
I = (\lambda\phi)^{n}{\beta} sinh(\alpha V)+\chi(e^{\gamma V}-1),
\end{eqnarray}
where $\alpha,\beta,\gamma, \lambda$ and $\chi$ is fitting constants, and
$\phi$ is the flux injected to the cell by the external voltage. The first part of Equation~(\ref{equ:model_two_inter}) represents the memristor behaviors of ON state and the other part describes the Schottky-like behavior.



\subsection{Log-normal Switching Time Distribution of Memristor}
%The combination effects of the Schottky-like and ohmic-like interfaces of the memristor cell, as well as the existence of the geometry process variation, results in the

With the aggressive technology scaling, process variability becomes a
critical issue which may result in device parameter fluctuations and
therefore affect the performance and the reliability of devices. Prior studies show that , the geometry variation may exist in each dimension of the memristor~\cite{memristor:dimin}\cite{memristor:ASPDAC}. Since the electrical behaviors of memristor, such as write/read speed and energy consumption, depend on the geometry parameters to a great extent, the impact of geometry variation on the memristor cell should be taken into full consideration during the design of the memristor-based memory.

Besides the geometry variability, other uncertainties of memristor's physical
characteristics, such as the concentration of oxygen vacancies, also play
important roles in the resistance switching behaviors of the memristor cell.
It has been reported that, under the impact of all of these variations, the
switching time of memristor cells with identical internal structure follows a
log-normal distribution. The probability density function (PDF) and the
cumulative distribution function (CDF) can be expressed as:

\vspace{-10pt}
%\begin{eqnarray}
\begin{align}
\label{equ:CDF}
f(t; \tau, \sigma) & = \frac{1}{\sqrt{2\pi}t\sigma}\textmd{exp}[-\frac{(\textmd{ln}(t/\tau))^2}{2\sigma^2}]\\
F(t; \tau, \sigma) & = \frac{1}{2}{\textmd{erfc}}[-\frac{(\textmd{ln}(t/\tau))}{\sqrt{2}\sigma}],
\end{align}
%\end{eqnarray}
where $t$ is the switching time of the memristor cell, $\tau$ is the median
switching time under certain external bias voltage, and $\sigma$ is the standard
deviation of $\tau$. Also, the median switching time has an exponential
dependency to the external voltage, and there is no significant relationship between the standard deviation $\tau$ and the voltage~\cite{memristor:logarithm}. Figure~\ref{fig:cdf} shows the PDF and CDF of switching time under different external bias
voltage. It can be easily observed that a higher input voltage will increase the probability of shorter switching time significantly. Therefore, increasing the programming voltage is a good method to improve the reliability of the memristor-based memory. Besides, for a given voltage constraint, the switching probability of a memristor cell increases with the switching time. Therefore, we can also increase the write latency to satisfy the relatively high reliability requirement of a memory cell.

%large write
%latency will also benefit the reliability of the memristor cell.

\begin{figure}
\centering
  % Requires \usepackage{graphi cx}
%  \includegraphics[width=0.5\textwidth]{./figures/cdf_sim.pdf}
    \includegraphics[width=0.35\textwidth]{./figures/cdf_shu.pdf}
  \vspace{-10pt}
  \caption{CDF and PDF of the switching time under different voltage input}\label{fig:cdf}
  \vspace{-15pt}
\end{figure}


%The thin film and spintronic memristors are all based on the thin film deposition technology. Among the aforementioned three dimensions, the width and the length variations are mainly resulted from the line-edge roughnesses (LERs), which are caused by random uncertainties in the process of lithograph and etching. Besides, the thickness variation is caused by the uncertainty of the deposition process.

%The impact process variation on thin film memristor memory is studied by Niu~\cite{memristor:dimin} and a more detailed analysis on the impact of geometry variations on both thin film and spintronic memristor is carried out by Hu~\cite{memristor:ASPDAC}. The method to generate the overall process variation of the memristor cell is shown in Figure.\ref{fig:pvg}. The fluctuations in the vertical direction contain the thickness variation and the resistance variation of the electrode contacts. In this paper, both of the fluctuations are modeled by assuming that they follow the Gaussian distribution. The fluctuations in the horizontal direction are resulted from the LER and the line-width roughness (LWR), which are generated via Gaussian autocorrelation~\cite{memristor:LER}. %

%\begin{figure}
%\centering
%  % Requires \usepackage{graphicx}
%  \includegraphics[width=0.45\textwidth]{./figures/pvgeneration.pdf}\\
%  \vspace{-10pt}
%  \caption{The flow to generate 3-D process variation}\label{fig:pvg}
%  \vspace{-10pt}
%\end{figure}
\subsection{Impact of the Log-normal Switching Time Distribution}
For a memristor-based memory, the log-normal switching time distribution may induce several severe problems on reliability, speed and power consumption. Generally, the uncertainty of the switching behaviors affects the memristor-based memory in the following aspects:
\begin{enumerate}
  \item \textbf{Reliability}: For the memristor-based memory, the
      information is represented as the resistance of the cell. As
      mentioned, the probability of the switching time follows a
      log-normal distribution and can not ensure the memristor cell is
      switched to the state with required resistance after a write
      operation. This uncertainty is not desirable and is harmful to the
      reliability of the memristor-based memory.
  \item \textbf{Energy Consumption}: To overcome the aforementioned
      reliability issue, more reliable program operation is required. As discussed, a more reliable program operation can be obtained by either boosting the write voltage or increasing the write latency. However, both of them will influence the energy consumption of the memristor-based memory. Especially, in order to achieve a relatively low bit error rate, the program voltage and write latency should be designed for the worst case situation. As such, lots of the cell are over programmed with a huge amount of energy waste.
  \item \textbf{Performance}: In addition to the energy consumption, the performance is also affected by the uncertainty of the switching
      behavior. From Figure~\ref{fig:cdf} we can see that, with bias
      voltage $V=7V$, in order to increase the switching probability from
      0.8 to 0.9, the switching time increases by 33\%, which will
      significantly reduce the performance of the memory array.
\end{enumerate}

%In this paper, a random variable $\emph{E}_{\rho}$ is used to represent the write (SET or RESET) energy consumption of the memristor cell, where the parameter $\rho$ indicates the internal states after the write operation. Thus, the SET operation is denoted as $E_1$ and RESET is denoted as $E_0$.

In the ideal condition, assuming the switching time variation is negligible, the write (SET or RESET) energy consumption of the memristor cell sticks to a fixed value. However, if we consider the variation of the switching time, the energy consumption is no longer a constant but follows a particular distribution for each combination of ($V,\tau$, and $\sigma$) set. Figure~\ref{fig:energy} shows the write energy and latency fluctuations, with different program voltage $V$ and standard deviation $\sigma$. Note that, a reliable write operation should be strong enough to ensure all of the cells can be written to the desired state. In this example, we assume the error rate of the write operation is less than $10^{-5}$. Figure~\ref{fig:energy} shows that, the program energy and latency increase dramatically with the decrease of program voltage as well as the increase of standard deviation. Obviously, increasing the program voltage is a effective way to reduce the write energy and latency at the same time. However, note that the program voltage is mainly determined by the physical characteristics of the memristor cell itself, including materials, processing technology, forming method, and cell size, and limited by many other design constraints. Therefore, in this paper, we assume that the upper bound of the program voltage is fixed at $V_{max}$. As mentioned, for a given program voltage, the switching probability of a memristor cell increases monotonically with increasing of switching time. Besides, the write energy is the integral of write voltage on time. Thus, the switching probability (or error rate) has a direct relationship with the write energy, which is shown in Figure~\ref{fig:diffp}. It is shown that the write energy increases with the decrease of error rate requirement. Therefore, in this paper, we proposed to use the ECC code to relax the reliability requirement of a single memristor cell, which could improve the energy efficiency and the performance of the memory array while maintaining the low error rate of the entire memory array.

%For example, in Figure.\ref{fig:variation}, the safety region is defined as 0.7 to 1. In order to overcome the impact of process variation, the write energy increases from 0.59 to 0.74 for spintronic memristor and increases from 0.18 to 0.29 for the thin film memristor.

\begin{figure}
\centering
   \includegraphics[width=0.37\textwidth]{./figures/energy_shu.pdf}\\
 \vspace{-10pt}
  \caption{Normalized write energy/latency comparison (Error Rate=0.00001).}\label{fig:energy}
  \vspace{-5pt}
\end{figure}

\begin{figure}
\centering
 \vspace{-30pt}
   \includegraphics[width=0.50\textwidth]{./figures/diffp_3.pdf}\\
 \vspace{-40pt}
  \caption{Write energy variation with different error rate.}\label{fig:diffp}
  \vspace{-10pt}
\end{figure}
%\begin{figure}
%\centering
%   \includegraphics[width=0.35\textwidth]{./figures/variation.pdf}\\
%  \vspace{-10pt}
%  \caption{Impact of process variation on write energy.}\label{fig:variation}
%  \vspace{-10pt}
%\end{figure}

%The LER and the consequent line-width roughness (LWR) have been
%comprehensivly studied in [10] [14]. The process variation in the cross
%section area is introduced due to the lithographic patterning method, and
%is similar to LER and LWR. As shown in Fig. 6, the LER exists in all of
%the four edges of the cross section. Thus, we should model the LER for
%each edge and evaluate the area variation resulting from the LER. In this
%paper, the LER is generated via a Gaussian autocorrelation function [9].
%The algorithm to generate the LER is shown in Fig. 10. This algorithm
%starts from a power spectrum for Gaussian autocorrelation function, which
%is denoted as


%device parameter fluctuations induced by process variations such as
%line-edge roughnesses (LERs), oxide thickness fluctuations (OTFs), and
%random discrete dopants (RDDs) have become critical issues in affecting
%the performance of devices Among these variations, LER is one of the
%random variations caused by random uncertainties in the process of
%lithograph and etching. It results in a random deviation of line edge
%print-images from its ideal pattern [10]. Since LER does not decrease as
%the device shrinks due to fundamental problems with the molecular
%structure of the photoresist, it is reported as the key variation problem
%of device fluctuations in sub-45nm dimensions [11]. Because the memristor
%is implemented on the basis of the thin-film deposition technology, it is
%important to evaluate the impact of the process variations on the
%electrical behavior of the memristor.

\subsection{Bit Error Rate Analysis}
%In this section, the theoretical bit error rates of different
%ECC-memristor schemes are analyzed.

%\subsubsection{ECC code}

In this paper, we assume the maximum size of the data block is 512 bits or 64 bytes, which is consistent with the recent research on non-volatile
memory~\cite{ECC:ECP}\cite{ECC:FreeP}. A $(n,k)$ ECC code indicates that
total $n-k$ bits are attached to $k$ information bits to construct a
codeword with length of $n$. An overview of the proposed system architecture
is shown in Figure~\ref{fig:ecc_memory}(a). The memristor array is
implemented in either cross-point architecture or the CMOS based
architecture. In total 512 information bits is encoded and decoded with
$N_{ECC}$ bits of ECC data.

\begin{figure}
\centering
   \includegraphics[width=0.5\textwidth]{./figures/ecc_memory.pdf}\\
  \vspace{-10pt}
  \caption{(a) The architecture of ECC for memristor memory. (b) Subblocks with ECC overhead.}\label{fig:ecc_memory}
  \vspace{-5pt}
\end{figure}

\begin{figure} \centering
   \includegraphics[width=0.45\textwidth]{./figures/512BER.pdf}\\
  \vspace{-5pt}
  \caption{Error rate of a 512 bits block ($p$ is the error rate of a single memristor cell after write operation). }\label{fig:512BER}
  \vspace{-10pt}
\end{figure}
As mentioned, Figure~\ref{fig:diffp} reveals the relationship between the reliability and write energy of the memristor cell: in order to increase the reliability of the write operation, more energy is needed to program the memristor cell. Therefore, a variable, $p(E)$, is used to indicate the error rate after the write operation with energy $E$. Consequently, the memristor is programmed into the desired state with a probability of $1-p(E)$. Then, let us firstly consider the scenario that the whole 512-bits information block is encoded
and decoded together with a ECC code with $m$ bits error correction
capability. Then the error rate after ECC can be calculated as:

\begin{eqnarray}
\label{equ:p}
P_{err}=1-\sum_{i=0}^m{512\choose i}\cdot{p(E)}^i\cdot(1-p(E))^{512-i},
\end{eqnarray}

Figure~\ref{fig:512BER} shows the probabilities of error occur in a 512 bits block under different $p_E$ and ECC codes. In this figure, the BCH\_$i$ represents the BCH code which can correct $i$-bit errors at the same time.
This figure shows that, the probability of error occurs in the block can be
reduced, either by more reliable write operation or by more powerful ECC
codes.


\begin{figure}
\centering
   \includegraphics[width=0.35\textwidth]{./figures/ECC1.pdf}\\
  \vspace{-5pt}
  \caption{Error rate for 512 bits block with SEC-DED code (The 512 bits block is evenly divided into $N$ subblocks; $p$ is the error rate of a single memristor cell after write operation).}\label{fig:ECC1}
  \vspace{-10pt}
\end{figure}
\begin{figure}
\centering
   \includegraphics[width=0.35\textwidth]{./figures/ECC2.pdf}\\
  \vspace{-5pt}
  \caption{Error rate for 512 bits block with BCH\_2 code (The 512 bits block is evenly divided into $N$ subblocks; $p$ is the error rate of a single memristor cell after write operation).}\label{fig:ECC2}
  \vspace{-10pt}
\end{figure}
Then we evenly divide the 512 bits into $N$ separate subblocks
($N=1,2,4,8\cdots$), with each subblock has the length of $512/N$. Additionally, as shown in Figure~\ref{fig:ecc_memory}, each subblock has its own ECC circuit and then Figure~\ref{fig:ECC1} and \ref{fig:ECC2} show the error rates for different values of $N$ with SEC-DED code and BCH\_2 code. Obviously, the increase of $N$ can also reduce the error rate for the whole block. However, the overhead in area, energy, and latency of these schemes (either increasing the write reliability or increasing $N$ ) should not be ignored. The overhead of the area results from the ECC circuits and the parity check bits. The parity bits needed in each schemes can be calculated easily and are list in Table~\ref{tab:ovhd}. Nevertheless, the area overhead of ECC circuit, as well as energy/latency overhead, can not be evaluated directly and will be discussed detailed in Section~\ref{sec:experiment}.

%The tradeoff between latency and energy overhead for different ECC scheme is presented in Section~\ref{sec:experiment}.



\begin{table}[!htb]
\scriptsize \centering \caption{Cell Overhead of ECC codes (The 512 bits block is evenly divided into $N$ subblocks, each subbolck has its own ECC code; $N_{ECC}$ is the total parity bits of the whole block).}\label{tab:ovhd}
\begin{tabular}{c|c|c|c|c|c}
  \hline  \hline
  N & 1 & 2 & 4 & 8 & 16\\
      ~  & $N_{ECC}$/\% & $N_{ECC}$/\% & $N_{ECC}$/\% & $N_{ECC}$/\% & $N_{ECC}$/\%\\
    \hline
    SEC-DED & 11/ 2.1\% &	 20/ 3.9\% &	 36/ 7.0\%	&	 64/12.5\%	&	 112/ 21.9\% \\
    BCH\_2  & 20/ 3.9\% &	 36/ 7.0\% &	 64/12.5\%	&	112/21.9\%	&	 192/ 37.5\% \\
    BCH\_3  & 30/ 5.9\% &	 54/10.5\% &	 96/18.8\%	&	168/32.8\%	&	 288/ 56.3\% \\
    BCH\_4  & 40/ 7.8\% &	 72/14.1\% &	128/25.0\%	&	224/43.8\%	&	 384/ 75.0\% \\
    BCH\_5  & 50/ 9.8\% &	 90/17.6\% &	160/31.3\%	&	280/54.7\%	&	 480/ 93.8\% \\
    BCH\_6  & 60/11.7\% &	108/21.1\% &	192/37.5\%	&	336/65.6\%	&	 576/112.5\% \\
%    BCH\_7  & 70/13.7\% &	126/24.6\% &	224/43.8\%	&	392/76.6\%	&	 672/131.2\% \\
  \hline
\end{tabular}
\vspace{-15pt}
\end{table}
